//爬楼梯使用递归
// const climp = (n) => {
//   if (n === 1) return 1;
//   if (n === 2) return 2;

//   return climp(n - 1) + climp(n - 2);
// };

// const num = climp(10);
// console.log(num);

//优化版 ： 重复算过的用数组存储起来

const climp1 = (n) => {
  const array = [];
  const step = (n) => {
    if (n <= 0) return 0;
    if (n === 1) return 1;
    if (n === 2) return 2;
    if (array[n]) return array[n];

    array[n] = step(n - 1) + step(n - 2);
    console.log("数组=>", array);
    return array[n];
  };

  return step(n);
};

console.log(climp1(4));

//使用循环

const climp2 = (n) => {
  const array = [1, 1];
  if (n === 1) return 1;
  if (n === 2) return 2;

  for (let i = 2; i <= n; i++) {
    array[i] = array[i - 1] + array[i - 2];
  }

  return array[n];
};

console.log(climp2(10));
